package com.major.tree.heapsorting;

public class HeapSort {
    public static void heapSort(int[] arr) {
        // 第一次调成大顶堆。从最后一个非叶子结点往上调整
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            adjustHeap(arr, i, arr.length);
        }

        int temp = 0;
        for (int i = arr.length-1; i > 0 ; i--) {
            // 顶部与末尾交换位置
            temp = arr[i];
            arr[i] = arr[0];
            arr[0] = temp;
            // 循环调整为大顶堆。从上往下调整，每次调整结束都交换位置
            adjustHeap(arr,0,i);
        }
    }

    // 调成大顶堆
    private static void adjustHeap(int[] arr, int index, int length) {
        int temp = arr[index];
        // 先找左子结点
        for (int j = index * 2 + 1; j < length; j = j * 2 + 1) {
            // 左小于右,指向右
            if (j + 1 < length && arr[j] < arr[j + 1]){
                j++;
            }

            // j就是两个子结点大的那个，再和父结点(index)比较，交换，
            if (arr[j] > temp){
                arr[index] = arr[j];
                index = j;          //*****，继续比较他的左子结点，因为前面可能已经调整了，破环了结构
            }else {
                break;
            }
            arr[index] = temp;

        }
    }
}
